package leetcode.trie.p211;

import java.util.TreeMap;
/**
 * 
 * @Title: WordDictionary.java 
 * @Package leetcode.trie.p211 
 * @Description: 211. 添加与搜索单词 - 数据结构设计
 *                  递归实现
 * @author CandyWall   
 * @date 2021年1月10日 下午8:32:14 
 * @version V1.0
 */
public class WordDictionary1 {
    private class Node {
        public boolean isWord;
        TreeMap<Character, Node> next;

        public Node() {
            this.isWord = false;
            this.next = new TreeMap<>();
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public WordDictionary1() {
        root = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!cur.next.containsKey(c)) {
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        cur.isWord = true;
    }

    /**
     * Returns if the word is in the data structure. A word could contain the
     * dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        return match(root, word, 0);
    }
    
    private boolean match(Node node, String word, int index) {
        if(index == word.length()) {
            return node.isWord;
        }
        char c = word.charAt(index);
        if(c != '.') {
            if(!node.next.containsKey(c))
                return false;
            return match(node.next.get(c), word, index + 1);
        } else  {
            for(Character ch : node.next.keySet()) {
                if(match(node.next.get(ch), word, index + 1)) {
                    return true;
                }
            }
            return false;
        }
    }
    
    public static void main(String[] args) {
        WordDictionary1 wordDictionary = new WordDictionary1();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        System.out.println(wordDictionary.search("pad"));// return False
        System.out.println(wordDictionary.search("bad")); // return True
        System.out.println(wordDictionary.search(".ad")); // return True
        System.out.println(wordDictionary.search("b..")); // return True
    }
}